/*
 * Project: Sudoku Solver
 * File: grid.c
 *
 * Copyright (C) 2009 Daniel Meekins
 * Contact: dmeekins - gmail
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "grid.h"

/* Internal functions -  prototypes */
void grid_update_grids(grid_t *g);
void grid_update_rows(grid_t *g);
void grid_update_cols(grid_t *g);
void grid_get_possible_row_bits(grid_t *g, uint32_t row, uint32_t col);
void grid_get_possible_col_bits(grid_t *g, uint32_t row, uint32_t col);
void grid_get_possible_grid_bits(grid_t *g, uint32_t row, uint32_t col);


grid_t *grid_new(uint32_t nums[ROWS][COLS])
{
    grid_t *g;
    uint32_t r, c;
    
    if((g = (grid_t *)malloc(sizeof(grid_t))) == NULL)
        return NULL;
    
    if(nums)
    {
        for(r = 0; r < ROWS; r++)
            for(c = 0; c < COLS; c++)
                g->cells[r][c] = cell_new(nums[r][c]);
    }
    else
    {
        for(r = 0; r < ROWS; r++)
            for(c = 0; c < COLS; c++)
                g->cells[r][c] = cell_new(0);
    }
    
    return g;
}

int grid_check(grid_t *g)
{
    uint32_t i, j, r, c, k;
    uint32_t nums[CELL_MAX_NUM];
    
    // check cols
    for(i = 0; i < COLS; i++)
    {
        memset(nums, 0, sizeof(nums));
        
        for(j = 0; j < ROWS; j++)
        {
            if(cell_issolved(grid_cell_at(g, i, j)))
                nums[grid_num_at(g, i, j)-1]++;
        }

        for(i = 0; i < CELL_MAX_NUM; i++)
        {
            if(nums[i] > 1)
                return -1;
        }
    }
    
    
    // check rows
    for(j = 0; j < ROWS; j++)
    {
        memset(nums, 0, sizeof(nums));
        
        for(i = 0; i < COLS; i++)
        {
            if(cell_issolved(grid_cell_at(g, i, j)))
                nums[grid_num_at(g, i, j)-1]++;
        }

        for(i = 0; i < CELL_MAX_NUM; i++)
        {
            if(nums[i] > 1)
                return -1;
        }
    }
    
    // check grids    
    for(r = 0; r < G_ROWS; r++)
    {
        for(c = 0; c < G_COLS; c++)
        {
            memset(nums, 0, sizeof(nums));

            for(i = 0; i < ROWS / G_ROWS; i++)
            {
                for(j = 0; j < COLS / G_COLS; j++)
                {
                    if(cell_issolved(grid_local_cell_at(g, r, c, i, j)))
                    {
                        k = cell_get_num(grid_local_cell_at(g, r, c, i, j));
                        nums[k-1]++;
                    }
                }
            }

            for(k = 0; k < CELL_MAX_NUM; k++)
            {
                if(nums[k] > 1)
                    return -1;
            }
        }
    }

    return 1;
}

void grid_update(grid_t *g)
{
    if(g)
    {
        grid_update_grids(g);
        grid_update_rows(g);
        grid_update_cols(g);
    }
}

void grid_update_rows(grid_t *g)
{
    uint32_t i, j;
    
    for(i = 0; i < ROWS; i++)
        for(j = 0; j < COLS; j++)
            if(!cell_issolved(grid_cell_at(g, i, j)))
                grid_get_possible_row_bits(g, i, j);
}

void grid_update_cols(grid_t *g)
{
    uint32_t i, j;
    
    for(i = 0; i < COLS; i++)
        for(j = 0; j < ROWS; j++)
            if(!cell_issolved(grid_cell_at(g, i, j)))
                grid_get_possible_col_bits(g, i, j);
}

void grid_update_grids(grid_t *g)
{
    uint32_t i, j;
    
    for(i = 0; i < ROWS; i++)
        for(j = 0; j < COLS; j++)
            if(!cell_issolved(grid_cell_at(g, i, j)))
                grid_get_possible_grid_bits(g, i, j);
}

void grid_get_possible_row_bits(grid_t *g, uint32_t row, uint32_t col)
{
    uint32_t j;
    cell_t *poss_bits;
    cell_t *curr_cell;
    
    if(!g || row >= ROWS || col >= COLS)
        return;
    
    if((poss_bits = cell_new(0)) == NULL)
        return;
    
    /* find the numbers the cell can't be */
    for(j = 0; j < COLS; j++)
        if(cell_issolved(grid_cell_at(g, row, j)))
            cell_diff(poss_bits, poss_bits, grid_cell_at(g, row, j));
    
    /* get the current cell and take the intersection of the set of numbers
       that cell can be with new set of possible numbers, and set the result
       to the current cell. */
    curr_cell = grid_cell_at(g, row, col);
    cell_intersect(curr_cell, curr_cell, poss_bits);
    
    cell_free(poss_bits);
}

void grid_get_possible_col_bits(grid_t *g, uint32_t row, uint32_t col)
{
    uint32_t i;
    cell_t *poss_bits;
    cell_t *curr_cell;
    
    if(!g || row >= ROWS || col >= COLS)
        return;
    
    if((poss_bits = cell_new(0)) == NULL)
        return;
    
    /* find the numbers the cell can't be */
    for(i = 0; i < ROWS; i++)
        if(cell_issolved(grid_cell_at(g, i, col)))
            cell_diff(poss_bits, poss_bits, grid_cell_at(g, i, col));
    
    /* get the current cell and take the intersection of the set of numbers
       that cell can be with new set of possible numbers, and set the result
       to the current cell. */
    curr_cell = grid_cell_at(g, row, col);
    cell_intersect(curr_cell, curr_cell, poss_bits);
    
    cell_free(poss_bits);
}

void grid_get_possible_grid_bits(grid_t *g, uint32_t row, uint32_t col)
{
    uint32_t gr, gc;
    uint32_t i, j;
    cell_t *poss_bits;
    cell_t *curr_cell;
    
    if(!g || row >= ROWS || col >= COLS)
        return;
    
    if((poss_bits = cell_new(0)) == NULL)
        return;
    
    /* get the current sub-grid coordinates the cell is in */
    gr = GRID_SUB_ROW(row);
    gc = GRID_SUB_COL(col);
    
    /* find the numbers the cell can't be */
    for(i = gr * G_ROWS; i < (gr * G_ROWS) + (ROWS / G_ROWS); i++)
        for(j = gc * G_COLS; j < (gc * G_COLS) + (COLS / G_COLS); j++)
            if(cell_issolved(grid_cell_at(g, i ,j)))
                cell_diff(poss_bits, poss_bits, grid_cell_at(g, i, j));
    
    /* get the current cell and take the intersection of the set of numbers
       that cell can be with new set of possible numbers, and set the result
       to the current cell. */
    curr_cell = grid_cell_at(g, row, col);
    cell_intersect(curr_cell, curr_cell, poss_bits);
    
    cell_free(poss_bits);
}

cell_t *grid_cell_at(grid_t *g, uint32_t r, uint32_t c)
{
    if(!g || r >= ROWS || c >= COLS)
        return NULL;
    
    return g->cells[r][c];
}

cell_t *grid_local_cell_at(grid_t *g, uint32_t grid_r, uint32_t grid_c,
                           uint32_t sub_r, uint32_t sub_c)
{
    return grid_cell_at(g, grid_r*G_ROWS + sub_r, grid_c*G_COLS + sub_c);
}

uint32_t grid_num_at(grid_t *g, uint32_t r, uint32_t c)
{
    if(!g || r >= ROWS || c >= COLS)
        return 0;
    
    return cell_get_num(g->cells[r][c]);
}

void grid_set_cell_num(grid_t *g, uint32_t num, uint32_t r, uint32_t c)
{
    int update = 1;
    int i, j;
    
    if(!g || r >= ROWS || c >= COLS)
        return;
    
    /* check the column */
    for(i = 0; i < ROWS && update; i++)
        if(cell_get_num(grid_cell_at(g, i, c)) == num)
            update = 0;
    
    /* check the row */
    for(j = 0; j < COLS && update; j++)
        if(cell_get_num(grid_cell_at(g, r, j)) == num)
            update = 0;
    
    /* check the subgrid */
    for(i = 0; i < ROWS / G_ROWS && update; i++)
        for(j = 0; j < COLS / G_COLS && update; j++)
            if(cell_get_num(
                   grid_local_cell_at(
                       g, GRID_SUB_ROW(r), GRID_SUB_COL(c), i, j)) == num)
                update = 0;
    
    if(update)
        cell_set_num(grid_cell_at(g, r, c), num);
}

void grid_set_local_cell_num(grid_t *g, uint32_t num, 
                             uint32_t gr, uint32_t gc, uint32_t r, uint32_t c)
{
    grid_set_cell_num(g, num, GRID_GLOBAL_ROW(gr, r), GRID_GLOBAL_COL(gc, c));
}

int grid_sub_num_solved(grid_t *g, uint32_t gr, uint32_t gc)
{
    int r, c;
    int count;
    
    count = 0;
    
    for(r = 0; r < ROWS / G_ROWS; r++)
        for(c = 0; c < COLS / G_COLS; c++)
            if(cell_issolved(grid_local_cell_at(g, gr, gc, r, c)))
                count++;
    
    return count;
}

int grid_issolved(grid_t *g)
{
    int i, j;
    
    for(i = 0; i < ROWS; i++)
        for(j = 0; j < COLS; j++)
            if(!cell_issolved(grid_cell_at(g, i, j)))
                return 0;
    
    return 1;
}

void grid_print(grid_t *g)
{
    uint32_t i, j;
    
    printf("/ ");
    for(j = 0; j < COLS + (COLS / G_COLS) - 1; j++)
        printf("- ");
    printf("\\\n");
    
    for(i = 0; i < ROWS; i++)
    {
        printf("| ");
        
        if(i > 0 && i % (ROWS / G_ROWS) == 0)
        {
            for(j = 0; j < COLS + (COLS / G_COLS) - 1; j++)
                printf("- ");
            printf("|\n| ");
        }
        
        for(j = 0; j < COLS; j++)
        {
            if(j > 0 && j % (COLS / G_COLS) == 0)
                printf("| ");
            if(cell_issolved(grid_cell_at(g, i, j)))
                printf("%d ", (int)grid_num_at(g, i, j));
            else
                printf("  ");
        }
        
        printf("|\n");
    }
    
    printf("\\ ");
    for(j = 0; j < COLS + (COLS / G_COLS) - 1; j++)
        printf("- ");
    printf("/\n");
}

void grid_print_full(grid_t *g)
{
    uint32_t i, j;
    int k;
    
    printf("/ ");
    for(j = 0; j < COLS + (COLS / G_COLS) - 1; j++)
        printf("- ");
    printf("\\   ");

    printf("/ ");
    for(j = 0; j < 47; j++)
        printf("- ");
    printf("\\\n");
    
    for(i = 0; i < ROWS; i++)
    {
        printf("| ");
        
        if(i > 0 && i % (ROWS / G_ROWS) == 0)
        {
            for(j = 0; j < COLS + (COLS / G_COLS) - 1; j++)
                printf("- ");
            printf("|   | ");

            for(j = 0; j < 47; j++)
                printf("- ");
            printf("|\n| ");
        }

        /* Print regular side on left */
        
        for(j = 0; j < COLS; j++)
        {
            if(j > 0 && j % (COLS / G_COLS) == 0)
                printf("| ");
            if(cell_issolved(grid_cell_at(g, i, j)))
                printf("%d ", (int)grid_num_at(g, i, j));
            else
                printf("  ");
        }

        printf("|   | ");

        /* Print extended bit side on right */
        
        for(j = 0; j < COLS; j++)
        {
            if(j > 0 && j % (COLS / G_COLS) == 0)
                printf("| ");
            for(k = CELL_MAX_NUM - 1; k >= 0; k--)
                printf("%d", (g->cells[i][j]->num >> k) & 0x1);
            printf(" ");
        }

        printf("|\n");
    }
    
    printf("\\ ");
    for(j = 0; j < COLS + (COLS / G_COLS) - 1; j++)
        printf("- ");
    printf("/   ");

    printf("\\ ");
    for(j = 0; j < 47; j++)
        printf("- ");
    printf("/\n");
}

void grid_free(grid_t *g)
{
    int r, c;
    
    if(!g)
        return;
    
    for(r = 0; r < ROWS; r++)
        for(c = 0; c < COLS; c++)
            cell_free(g->cells[r][c]);
    
    free(g);
}
